package com.cet.algorithm.二叉树.左下角的值;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: algorithm
 * @description: 给定一个二叉树，在树的最后一行找到最左边的值。
 * @author: 陈恩涛
 * @create: 2022-07-21 15:19
 **/
public class LC513 {
    public static void main(String[] args) {
        final TreeNode root = new TreeNode(2, new TreeNode(1), new TreeNode(3));
        System.out.println(new LC513().findBottomLeftValue(root));
        System.out.println(new LC513().findBottomLeftValue2(root));
    }

    /**
     * 层级遍历
     */
    public int findBottomLeftValue(TreeNode root) {
        final Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int result = root.val;
        while (!queue.isEmpty()) {
            int len = queue.size();
            // boolean isBottom = true;
            // 记录一层最左侧节点的值
            result = queue.peek().val;
            while (len > 0) {
                final TreeNode cur = queue.poll();
                // isBottom = isBottom && cur.left == null && cur.right == null;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                len--;
            }
//            if (isBottom) {
//                break;
//            }
        }
        return result;
    }

    int Deep = 0;
    int value = 0;

    /**
     * 递归法
     *
     * 如果需要遍历整棵树，递归函数就不能有返回值。
     * 如果需要遍历某一条固定路线，递归函数就一定要有返回值！
     * @param root
     * @return
     */
    public int findBottomLeftValue2(TreeNode root) {
        findLeftValue(root, 1);
        return value;
    }

    private void findLeftValue(TreeNode node, int depth) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            // 同一层级只记录最左边的值
            if (depth > Deep) {
                Deep = depth;
                value = node.val;
            }
        }
        if (node.left != null) {
            findLeftValue(node.left, depth + 1);
        }
        if (node.right != null) {
            findLeftValue(node.right, depth + 1);
        }
    }

}
